package com.zhz.leetcode;

/**
 * 509. 斐波那契数
 * 斐波那契数（通常用F(n) 表示）形成的序列称为 斐波那契数列 。该数列由0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 * <p>
 * F(0) = 0，F(1)= 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * 给定n ，请计算 F(n) 。
 * <p>
 * 示例 1：
 * 输入：n = 2
 * 输出：1
 * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
 * <p>
 * 示例 2：
 * 输入：n = 3
 * 输出：2
 * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
 * <p>
 * 示例 3：
 * 输入：n = 4
 * 输出：3
 * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 * <p>
 * 提示：
 * 0 <= n <= 30
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fibonacci-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FibonacciNumber509 {

    public static void main(String[] args) {
        FibonacciNumber509 m = new FibonacciNumber509();
        int res = m.fib1(10);
        System.out.println(res);
    }

    /**
     * 递归方式
     */
    public int fib(int n) {
        return n <= 1 ? n : fib(n - 1) + fib(n - 2);
    }

    /**
     * 基于递归方式的优化
     * 为什么优化：
     * 因为会出现重复计算的问题，之后最后一个数才计算1次
     * 比如当n等于10的时候
     * -------------------f(10)
     * -----------------/      \
     * --------------f(8)      f(9)
     * -------------/   \      /   \
     * -----------f(6) f(7)  f(7)  f(8)
     * <p>
     * 可以看到f(8)会被计算两次
     * 如果是f(7) 那就会被计算3次
     * f(6) 会被计算5次
     * ...
     * 这个计算量有点大，因此这边考虑弄一个数组来保存数据，如果有数据就可以优先取数据，避免重复计算
     */
    public int fib2(int n) {
        int[] arr = new int[n + 1];
        return helper(n, arr);
    }

    public int helper(int n, int[] arr) {
        if (n <= 1) {
            return n;
        }
        if (arr[n] != 0) return arr[n];
        arr[n] = helper(n - 1, arr) + helper(n - 2, arr);
        return arr[n];
    }


    /**
     * 是动态规划
     */
    public int fib1(int n) {
        if (n < 2) {
            return n;
        }
        int res = 1;
        int last = 0;
        for (int i = 2; i <= n; i++) {
            int sum = res + last;
            last = res;
            res = sum;
        }
        return res;
    }

}
